package com.example.system.class14;

import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeSet;

/**
 * @Date 2022/8/6
 * @Author Jonathan
 * <p/>
 * 贪心算法：
 * 1) 最自然智慧的算法
 * 2) 局部最功利的标准 总是做出在当前看起来最好的选择
 * 3)
 * 4)
 * <p/>
 * 给定一个右字符串组成的数组str
 * 将所有的字符串都拼接起来 返回所有可能中 字典序最小的
 */
public class Code01_LowestStr {
    public static void main(String[] args) {
        String[] str = new String[]{"b", "ba", "ac", "bz"};
        final String ret = lowestStr(str);
        System.out.println(ret);
        System.out.println(lowestStr2(str));
    }


    // 对数器
    public static String lowestStr(String[] str) {
        return process(str).first();
    }

    public static String lowestStr2(String[] str) {
        Arrays.sort(str, new StringComparator());
        StringBuilder builder = new StringBuilder();
        for (String s : str) {
            builder.append(s);
        }
        return builder.toString();
    }

    public static TreeSet<String> process(String[] str) {
        TreeSet<String> ans = new TreeSet<>();
        if (str.length == 0) {
            ans.add("");
            return ans;
        }
        for (int i = 0; i < str.length; i++) {
            final String first = str[i];
            final String[] nexts = removeIndexStr(str, i);
            final TreeSet<String> next = process(nexts);
            for (String s : next) {
                // add 之后会自动排序
                ans.add(first + s);
            }
        }
        return ans;
    }

    private static String[] removeIndexStr(String[] str, int index) {
        final int length = str.length - 1;
        String[] arr = new String[length];
        int newIndex = 0;
        for (int i = 0; i < str.length; i++) {
            if (i == index) {
                continue;
            }
            arr[newIndex++] = str[i];
        }
        return arr;
    }

    // Comparator
    public static class StringComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            return (a + b).compareTo(b + a);
        }
    }
}
